#include <bits/stdc++.h>

using namespace std;

// simple version
// int main()
// {
//     int n, m, s, e, v;
//     cin >> n >> m;
//     vector<vector<int>> graph(n + 1, vector<int>(n + 1, INT_MAX));
//     for (int i = 0; i < m; i++)
//     {
//         cin >> s >> e >> v;
//         graph[s][e] = v;
//     }
//     vector<int> min_dist(n + 1, INT_MAX);
//     vector<bool> visited(n + 1, false);
//     min_dist[1] = 0;
//     for (int i = 1; i <= n; i++)
//     {
//         int cur = 1;
//         int value = INT_MAX;
//         for (int j = 1; j <= n; j++)
//         {
//             if (!visited[j] && min_dist[j] < value)
//             {
//                 cur = j;
//                 value = min_dist[j];
//             }
//         }
//         visited[cur] = true;
//         for (int j = 1; j <= n; j++)
//         {
//             if (!visited[j] && graph[cur][j] < INT_MAX && min_dist[cur] + graph[cur][j] < min_dist[j])
//             {
//                 min_dist[j] = min_dist[cur] + graph[cur][j];
//             }
//         }
//     }
//     if (min_dist[n] == INT_MAX)
//     {
//         cout << -1 << endl;
//     }
//     else
//     {
//         cout << min_dist[n] << endl;
//     }
//     return 0;
// }

// optimized version
struct Edge
{
    int to;
    int value;
    Edge(int t, int v) : to(t), value(v) {}
};
struct Compare
{
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        return a.second > b.second;
    }
};
int main()
{
    int n, m, s, e, v;
    cin >> n >> m;
    vector<list<Edge>> graph(n + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> s >> e >> v;
        graph[s].push_back({e, v});
    }
    vector<int> min_dist(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> que;
    int start = 1;
    int end = n;
    min_dist[start] = 0;
    que.push({1, 0});
    while (!que.empty())
    {
        pair<int, int> cur = que.top();
        que.pop();

        if (visited[cur.first])
        {
            continue;
        }

        visited[cur.first] = true;
        for (auto edge : graph[cur.first])
        {
            if (!visited[edge.to] && min_dist[cur.first] + edge.value < min_dist[edge.to])
            {
                min_dist[edge.to] = min_dist[cur.first] + edge.value;
                que.push({edge.to, min_dist[edge.to]});
            }
        }
    }
    if (min_dist[end] == INT_MAX)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << min_dist[end] << endl;
    }
    return 0;
}